package priorityQueue;

import java.util.Arrays;

public class MyPriorityQueue {
    private int[] data;
    private int useSize = 0;
    public MyPriorityQueue() {
        this(20);
    }
    public MyPriorityQueue(int capacity) {
        this.data = new int[capacity];
    }
    /**
     * 建堆的时间复杂度：
     *
     * @param array
     */
    public void createHeap(int[] array) {
        for(int i = 0; i < array.length; i++){
            data[useSize++] = array[i];
        }
        int child = useSize - 1;
        for(int parent =  (child - 1) / 2; parent >= 0; parent--){
            shiftDown(parent, useSize);
        }

    }

    /**
     * @param parent 是每棵子树的根节点的下标
     * @param size  是每棵子树调整结束的结束条件
     * 向下调整的时间复杂度：O(logn)
     */
    private void shiftDown(int parent,int size) {
        int child = 2 * parent + 1;
        while(child < size){
            //首先判断其是否有右孩子，有右孩子则比较左右孩子谁大
            if(child + 1 < size && data[child] < data[child + 1]){
                child++;    //右孩子大
            }
            //孩子大于父亲，进行交换
            if(data[child] > data[parent]){
                swap(child, parent);
            }
            parent = child;
            child = 2 * parent + 1;
        }
    }
    //交换函数
    private void swap(int index1, int index2){
        int tmp = data[index1];
        data[index1] = data[index2];
        data[index2] = tmp;
    }


    /**
     * 入队：仍然要保持是大根堆
     * @param val
     */
    public void push(int val) {
        if(isFull()){
            throw new RuntimeException("优先队列已满，无法插入新元素");
        }
        data[useSize] = val;
        //向上调整
        shiftUp(useSize);
        useSize++;
    }
    //向上调整
    private void shiftUp(int child) {
        int parent = (child - 1) / 2;
        //循环向上调整
        while(parent >= 0){
            //孩子大于父亲，进行交换
            if(data[child] > data[parent]){
                swap(child, parent);
            }
            child = parent;
            parent = (child - 1) / 2;
        }
    }
    //判满
    public boolean isFull() {
        return useSize == data.length;
    }

    /**
     * 出队【删除】：每次删除的都是优先级高的元素
     * 仍然要保持是大根堆
     */
    public int pollHeap() {
        if(isEmpty()){
            throw new RuntimeException("空优先队列，无元素可删除");
        }
        //记录堆顶元素用于返回
        int top = data[0];
        //堆顶元素与最后一个元素进行交换
        swap(0, useSize - 1);
        //有效元素个数件1，则删除堆顶元素
        useSize--;
        //向下调整，使其成为大堆
        shiftDown(0, useSize);
        return top; //返回删除的堆顶元素
    }
    //判空
    public boolean isEmpty() {
        return useSize == 0;
    }

    /**
     * 获取堆顶元素
     * @return
     */
    public int peekHeap() {
        if (isEmpty()){
            throw new RuntimeException("空优先队列，无法获取堆顶元素");
        }
        return data[0];
    }
    //获取优先级队列的长度
    private int size(){
        return useSize;
    }

    @Override
    public String toString(){
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for(int i = 0; i < size(); i++){
            stringBuilder.append(data[i]);
            if(i != size() - 1){
                stringBuilder.append(", ");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        int[] nums = new int[]{10,2,13,9,78,33,26,14,55,4,7,17,68,99,10086,128};
        //int[] nums = new int[]{10,2,13,9,78,33};
        System.out.println(nums.length);
        System.out.println(Arrays.toString(nums));

        MyPriorityQueue queue = new MyPriorityQueue();
        System.out.println(queue.isEmpty());
        queue.createHeap(nums);
        System.out.println(queue.isEmpty());
        System.out.println(queue);
        System.out.println(queue.size());
        System.out.println(queue.peekHeap());

        while(!queue.isEmpty()){
            System.out.print(queue.pollHeap() + " ");
        }
        System.out.println();

        System.out.println(queue.pollHeap());

    }
}
